package me.mingshan.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode.cn/problems/sum-root-to-leaf-numbers/description/
 *
 *
 * 给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。
 * 每条从根节点到叶节点的路径都代表一个数字：
 *
 * 例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
 * 计算从根节点到叶节点生成的 所有数字之和 。
 *
 * 叶节点 是指没有子节点的节点。
 *
 * @author hanjuntao
 * @date 2025/8/28 0028
 */
public class L_129_求根节点到叶节点数字之和 {

    public static void main(String[] args) {

        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(1);
        root.left.left = new TreeNode(3);
        root.right = new TreeNode(4);
        root.right.left = new TreeNode(1);
        root.right.right = new TreeNode(5);

        //          3
        //        1   4
        //     3     1  5

        System.out.println(sumNumbers(root));
    }

    /**
     * 使用一个list记录路径（通过dfs遍历），然后求和
     *
     * @param root
     * @return
     */
    public static int sumNumbers(TreeNode root) {
        if (root == null) {
            return 0;
        }
        List<String> result = new ArrayList<>();

        dfs(root, "", result);

        int sum = 0;
        for (String s : result) {
            sum += Integer.parseInt(s);
        }
        return sum;
    }

    private static void dfs(TreeNode root, String s, List<String> result) {
        if (root == null) {
            return;
        }

        if (s.isEmpty()) {
            s = String.valueOf(root.val);
        } else {
            s += root.val;
        }

        if (root.left == null && root.right == null) {
            System.out.println(s);
            result.add(s);
            return;
        }

        dfs(root.left, s, result);
        dfs(root.right, s, result);
    }

    /**
     * 能不能不使用额外的空间？
     *
     * 在使用额外的空间时，叶子节点进行计算时，进行到叶子节点后，将拼接的字符串返回
     *
     * 这里可以做一个优化，不拼接字符串，直接计算数字，如何计算数字：
     *
     *  第一次1
     *  第二次12
     *  第三次123
     *
     * 从上面可以发现，每次都是原来的数字*10，加上当前节点的值，
     * 所以数字的计算规则是：
     * i = node.val + 10 * i
     *
     * 其实就是十进制的构建过程。
     *
     *
     * 选择遍历方法：由于需要遍历所有路径，深度优先搜索（DFS）是自然的选择，因为它能有效地探索每条路径到底（即叶节点）。
     * 递归参数设计：在递归函数中，需要传递当前路径已构建的数字（称为 i），这样在到达叶节点时，可以直接返回该数字。
     *
     * 递归逻辑：
     *  基础情况：如果节点为空，返回0（表示没有贡献）。
     *  更新当前数字：对于每个节点，更新当前数字为 i * 10 + root.val。这确保了数字的正确构建。
     *  叶节点检查：如果当前节点是叶节点（左右子节点均为空），返回当前数字。
     *  递归左右子树：对于非叶节点，递归计算左右子树的和，并返回它们的和。
     * 初始化：从根节点开始，初始数字为0，但根节点的值会直接加入，因此第一个节点处理正确。
     *
     *
     * @param root
     * @return
     */
    public static int sumNumbers2(TreeNode root) {
        return dfs(root, 0);
    }

    /**
     * 现在模拟代码执行：
     * - 调用 `dfs(root=1, i=0)`
     *   - i 初始为0，所以更新 i = 1（因为 i==0，所以 i = root.val = 1）
     *   - 不是叶节点，所以递归调用左子树和右子树。
     *   - 调用 `dfs(left=2, i=1)`
     *     - i=1，不为0，所以更新 i = 2 + 10 * 1 = 12
     *     - 节点2是叶节点，返回12
     *   - 调用 `dfs(right=3, i=1)`
     *     - i=1，不为0，所以更新 i = 3 + 10 * 1 = 13
     *     - 节点3是叶节点，返回13
     *   - 返回 left + right = 12 + 13 = 25
     *
     * @param root
     * @param i
     * @return
     */
    private static int dfs(TreeNode root, int i) {
        if (root == null) {
            return 0;
        }

        // 第一次1
        // 第二次12
        // 第三次123
        if (i == 0) {
            i = root.val;
        } else {
            i = root.val + 10 * i;
        }

        // 节点是叶节点, 返回值
        if (root.left == null && root.right == null) {
            return i;
        }

        // 分别计算左右子树，并将返回值相加
        // 为什么要相加，因为题意要求算根节点到叶节点的数字，返回这些数之和
        int left = dfs(root.left, i);
        int right = dfs(root.right, i);

        return left + right;
    }
}
